//
//  BackTrackingSolution.hpp
//  leetcode
//
//  Created by Ellie on 2021/2/26.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef BackTrackingSolution_hpp
#define BackTrackingSolution_hpp

#include <stdio.h>
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

// 回溯算法
// 求解排列，组合，子集问题
// N-树的深度优先遍历，一般是前序遍历

// 找到决策树，剪枝（排序是剪枝的前提），根据逻辑确定深度，直接用track.size() == K，将满足条件的结果加入到列表中
// 优先画决策树
// 排列组合的剪枝操作都一致（排除重复的操作）

class BackTrackingSolution
{
public:
    // 剑指 Offer 38. 字符串的排列
    // 字符串的全排列
    vector<string> permutation(string s);
    void permutationstring(string& s, vector<string>& result, int position);
    
    //46. 全排列，无重复元素
    vector<vector<int>> permute(vector<int>& nums);
    void permute(vector<int>& nums, vector<vector<int>>& result, vector<int>& track);
    
    //47. 全排列 II 有重复元素
    vector<vector<int>> permuteUnique(vector<int>& nums);
    void permuteUnique(vector<int>& nums, vector<vector<int>>& result, vector<int>& track, vector<bool>& mark);
    
    //78. 子集 元素唯一
    vector<vector<int>> subsets(vector<int>& nums);
    void subsetdfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& track, int startindex);
    
    //90. 子集 II 元素可以重复
    vector<vector<int>> subsetsWithDup(vector<int>& nums);
    void subsetsWithDup(vector<int>& nums,  vector<vector<int>>& result, vector<int>& track, int startindex, vector<bool>& mark);
    
    //39.组合总和
    vector<vector<int>> combinationSum(vector<int>& candidates, int target);
    void combinationSum(vector<int>& candidates, vector<vector<int>>& result, int startindex, vector<int>& track, int target);
    
    //40. 组合总和 II
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target);
    void bracktrace(vector<int>& candidates, vector<vector<int>>& result, vector<int>& track, int target, int startindex, vector<bool>& mark);
    
    //77. 组合
    vector<vector<int>> combine(int n, int k);
    void combine(int n, int k, vector<vector<int>>& result, vector<int>& track);
    // N-Queen
    
    // 22. 括号生成
    vector<string> generateParenthesis(int n);
    void generateParenthesisDFS(int n, vector<string>& result, string& track, int left, int right);
    void generateParenthesisRecursion(int n, vector<string>& result, string track, int left, int right);
};

#endif /* BackTrackingSolution_hpp */
